import { Sort } from "../public/Sort"
import { DefaultCompare, ICompareFunction, CompareEnum } from "../public/Utils"

/**
 * 插入排序
 * 插入排序会将数组分为已排序区域和未排序区域，
 * 将未排序区域的数组项和已排序区域的数组进行大小比较，
 * 确立要插入的位置，然后将其插入到对应的位置。
 **/
export class InsertionSort<T> extends Sort<T> {
    constructor(array: Array<T> = [], compareFun: ICompareFunction = new DefaultCompare()) {
        super(array, compareFun)
    }
    sort(): void {
        //获取数组长度
        const { length } = this.array
        let temp: T
        //假设0号元素已经排好序，从1号元素开始遍历数组
        for (let i: number = 1; i < length; i++) {
            // 声明辅助变量存储当前i的位置以及其对应的值
            let j: number = i
            temp = this.array[i];
            // j-1位置的元素大于i号位置的元素就把j-1处的值移动到j处，最后j--
            while (this.compare.compare(this.array[j - 1], temp) === CompareEnum.BIGGER) { 
                this.array[j] = this.array[j -1]
                j--
            }
            //将temp放到正确位置
            this.array[j] = temp
        }
    }
}

// const InsertionSortTest = (): void => {
//     const array = [123, 424, 637, 154, 541]
//     const insertionSort: Sort<Number> = new InsertionSort<Number>(array)
//     insertionSort.sort()
//     console.log(array);
// }
// InsertionSortTest()